import java.util.*;

/**
 * @Description: 不含特殊楼层的最大连续楼层数
 * Alice 管理着一家公司，并租用大楼的部分楼层作为办公空间。Alice 决定将一些楼层作为 特殊楼层 ，仅用于放松。
 * 给你两个整数 bottom 和 top ，表示 Alice 租用了从 bottom 到 top（含 bottom 和 top 在内）的所有楼层。
 * 另给你一个整数数组 special ，其中 special[i] 表示  Alice 指定用于放松的特殊楼层。
 * 返回不含特殊楼层的 最大 连续楼层数。
 * <p>
 * 示例 1：
 * 输入：bottom = 2, top = 9, special = [4,6]
 * 输出：3
 * 解释：下面列出的是不含特殊楼层的连续楼层范围：
 * - (2, 3) ，楼层数为 2 。
 * - (5, 5) ，楼层数为 1 。
 * - (7, 9) ，楼层数为 3 。
 * 因此，返回最大连续楼层数 3 。
 * <p>
 * 示例 2：
 * 输入：bottom = 6, top = 8, special = [7,6,8]
 * 输出：0
 * 解释：每层楼都被规划为特殊楼层，所以返回 0 。
 * <p>
 * 提示
 * 1 <= special.length <= 105
 * 1 <= bottom <= special[i] <= top <= 109
 * special 中的所有值 互不相同
 * @Author: zhanglinxin
 * @date: 2025-01-06
 */
public class Solution202501 {
    public int maxConsecutive(int bottom, int top, int[] special) {
        Arrays.sort(special);
        int length = special.length;
        int max = special[0] - bottom;
        for (int i = 1; i < length; i++) {
            max = Math.max(max, special[i] - special[i - 1] - 1);
        }
        max = Math.max(max, top - special[length - 1]);
        return max;
    }

    /**
     * @Description: 给定两个字符串 s 和 t ，如果它们的编辑距离为 1 ，则返回 true ，否则返回 false 。
     * 字符串 s 和字符串 t 之间满足编辑距离等于 1 有三种可能的情形：
     * 往 s 中插入 恰好一个 字符得到 t
     * 从 s 中删除 恰好一个 字符得到 t
     * 在 s 中用 一个不同的字符 替换 恰好一个 字符得到 t
     * 示例 1：
     * 输入: s = "ab", t = "acb"
     * 输出: true
     * 解释: 可以将 'c' 插入字符串 s 来得到 t。
     * 示例 2:
     * 输入: s = "cab", t = "ad"
     * 输出: false
     * 解释: 无法通过 1 步操作使 s 变为 t。
     * 提示:
     * 0 <= s.length, t.length <= 104
     * s 和 t 由小写字母，大写字母和数字组成
     * @param: [java.lang.String, java.lang.String]
     * @return: java.lang.Boolean
     * @Author: zhanglinxin
     * @date: 2025/1/7 08:52
     */
    public Boolean isOneEditDistance(String s, String t) {
        if (s.equals(t)) {
            return false;
        }
        if (s.length() > t.length()) {
            return isOneEditDistance(t, s);
        }
        int m = s.length(), n = t.length();
        if ((m - n) * (m - n) > 1 || (m == 0 && n == 0)) {
            return false;
        }
        for (int i = 0; i < m; i++) {
            if (s.charAt(i) != t.charAt(i)) {
                if (m == n) {
                    return s.substring(i + 1).equals(t.substring(i + 1));
                }
                return s.substring(i).equals(t.substring(i + 1));
            }
        }
        return true;
    }

    /**
     * @Description: 给你一个字符串 num ，表示一个大整数。如果一个整数满足下述所有条件，则认为该整数是一个 优质整数 ：
     * 该整数是 num 的一个长度为 3 的 子字符串 。
     * 该整数由唯一一个数字重复 3 次组成。
     * 以字符串形式返回 最大的优质整数 。如果不存在满足要求的整数，则返回一个空字符串 "" 。
     * 注意：
     * 子字符串 是字符串中的一个连续字符序列。
     * num 或优质整数中可能存在 前导零 。
     * <p>
     * 示例 1：
     * 输入：num = "6777133339"
     * 输出："777"
     * 解释：num 中存在两个优质整数："777" 和 "333" 。
     * "777" 是最大的那个，所以返回 "777" 。
     * 示例 2：
     * 输入：num = "2300019"
     * 输出："000"
     * 解释："000" 是唯一一个优质整数。
     * 示例 3：
     * 输入：num = "42352338"
     * 输出：""
     * 解释：不存在长度为 3 且仅由一个唯一数字组成的整数。因此，不存在优质整数。
     * <p>
     * 提示：
     * 3 <= num.length <= 1000
     * num 仅由数字（0 - 9）组成
     * @param: [java.lang.String]
     * @return: java.lang.String
     * @Author: zhanglinxin
     * @date: 2025/1/8 15:16
     */
    public String largestGoodInteger(String num) {
        int length = num.length();
        String chars = "";
        for (int i = 0; i < length; i++) {
            if (i + 2 < length && num.charAt(i) == num.charAt(i + 1) && num.charAt(i) == num.charAt(i + 2)) {
                if (chars.isEmpty() || chars.charAt(0) <= num.charAt(i)) {
                    chars = num.substring(i, i + 3);
                }
            }
        }
        return chars;
    }

    /**
     * @Description: 给你两个字符串 word1 和 word2 。
     * 如果一个字符串 x 重新排列后，word2 是重排字符串的 前缀，那么我们称字符串 x 是 合法的 。
     * 请你返回 word1 中 合法 子字符串的数目。
     * 示例 1：
     * 输入：word1 = "bcca", word2 = "abc"
     * 输出：1
     * 解释：
     * 唯一合法的子字符串是 "bcca" ，可以重新排列得到 "abcc" ，"abc" 是它的前缀。
     * 示例 2：
     * 输入：word1 = "abcabc", word2 = "abc"
     * 输出：10
     * 解释：
     * 除了长度为 1 和 2 的所有子字符串都是合法的。
     * 示例 3：
     * 输入：word1 = "abcabc", word2 = "aaabc"
     * 输出：0
     * <p>
     * 解释：
     * 1 <= word1.length <= 105
     * 1 <= word2.length <= 104
     * word1 和 word2 都只包含小写英文字母
     * @param: [java.lang.String, java.lang.String]
     * @return: long
     * @Author: zhanglinxin
     * @date: 2025/1/9 09:40
     */
    public long validSubstringCount(String word1, String word2) {
        if (word1.length() < word2.length()) {
            return 0;
        }
        char[] arr1 = word1.toCharArray();
        char[] arr2 = word2.toCharArray();
        // 用来记录arr2中存在的字母种类
        int less = 0;
        // 记录arr2中字母数量
        int[] diff = new int[26];
        for (char c : arr2) {
            if (diff[c - 'a'] == 0) {
                less++;
            }
            diff[c - 'a']++;
        }
        int left = 0;
        long ans = 0;
        for (char c : arr1) {
            diff[c - 'a']--;
            if (diff[c - 'a'] == 0) {
                less--;
            }
            while (less == 0) {
                char outChar = arr1[left++];
                if (diff[outChar - 'a'] == 0) {
                    less++;
                }
                diff[outChar - 'a']++;
            }
            ans += left;
        }
        return ans;
    }

    public long validSubstringCount2(String word1, String word2) {
        long ans = 0;
        if (word1.length() < word2.length()) {
            return 0;
        }
        int[] charArr2 = new int[26];
        for (char c : word2.toCharArray()) {
            charArr2[c - 'a']++;
        }
        for (int start = 0; start < word1.length(); start++) {
            if (start + word2.length() > word1.length()) {
                break;
            }
            int[] charArr1 = new int[26];
            for (int end = start; end < word1.length(); end++) {
                charArr1[word1.charAt(end) - 'a']++;
                if (end - start + 1 >= word2.length() && isValid(charArr1, charArr2)) {
                    ans++;
                }
            }
        }
        return ans;
    }

    private boolean isValid(int[] charArr1, int[] charArr2) {
        for (int i = 0; i < 26; i++) {
            if (charArr1[i] < charArr2[i]) {
                return false;
            }
        }
        return true;
    }

    /**
     * @Description: 给你一个 非负 整数数组 nums 和一个整数 k 。
     * 如果一个数组中所有元素的按位或运算 OR 的值 至少 为 k ，那么我们称这个数组是 特别的 。
     * 请你返回 nums 中 最短特别非空子数组的长度，如果特别子数组不存在，那么返回 -1 。
     * <p>
     * 示例 1：
     * 输入：nums = [1,2,3], k = 2
     * 输出：1
     * 解释：
     * 子数组 [3] 的按位 OR 值为 3 ，所以我们返回 1 。
     * 注意，[2] 也是一个特别子数组。
     * <p>
     * 示例 2：
     * 输入：nums = [2,1,8], k = 10
     * 输出：3
     * 解释：
     * 子数组 [2,1,8] 的按位 OR 值为 11 ，所以我们返回 3 。
     * <p>
     * 示例 3：
     * 输入：nums = [1,2], k = 0
     * 输出：1
     * <p>
     * 解释：
     * 子数组 [1] 的按位 OR 值为 1 ，所以我们返回 1 。
     * <p>
     * 提示：
     * 1 <= nums.length <= 50
     * 0 <= nums[i] <= 50
     * 0 <= k < 64
     * @param: [int[], int]
     * @return: int
     * @Author: zhanglinxin
     * @date: 2025/1/16 13:20
     */
    public int minimumSubarrayLength(int[] nums, int k) {
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int value = 0;
            for (int j = i; j < nums.length; j++) {
                value |= nums[j];
                if (value >= k) {
                    res = Math.min(res, j - i + 1);
                    break;
                }
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    /**
     * @Description: 给你一个 非负 整数数组 nums 和一个整数 k .
     * 如果一个数组中所有元素的按位或运算 OR 的值 至少 为 k ，那么我们称这个数组是 特别的 。
     * 请你返回 nums 中 最短特别非空子数组的长度，如果特别子数组不存在，那么返回 -1 。
     * <p>
     * 示例 1：
     * 输入：nums = [1,2,3], k = 2
     * 输出：1
     * 解释：
     * 子数组 [3] 的按位 OR 值为 3 ，所以我们返回 1 。
     * <p>
     * 示例 2：
     * 输入：nums = [2,1,8], k = 10
     * 输出：3
     * 解释：
     * 子数组 [2,1,8] 的按位 OR 值为 11 ，所以我们返回 3 。
     * <p>
     * 示例 3：
     * 输入：nums = [1,2], k = 0
     * 输出：1
     * 解释：
     * 子数组 [1] 的按位 OR 值为 1 ，所以我们返回 1 。
     * @param: [int[], int]
     * @return: int
     * @Author: zhanglinxin
     * @date: 2025/1/17 11:07
     */
    public int minimumSubarrayLength1(int[] nums, int k) {
        // 如果目标值k为0，直接返回1，因为任何非零数字与0进行按位或运算都会得到非零结果。
        if (k == 0) {
            return 1;
        }
        int n = nums.length;
        // 初始化结果为比数组长度大1的值，表示尚未找到满足条件的子数组。
        int res = n + 1;
        // 当前遍历到的位置
        int current = 0;
        // sum用于记录当前窗口内所有元素按位或的结果。
        int sum = 0;
        // 开始遍历数组nums
        while (current < n) {
            // 内层循环尝试扩展窗口，直到sum >= k 或者到达数组末尾。
            while (current < n && sum < k) {
                // 将新加入窗口的元素与sum做按位或运算。
                sum |= nums[current++];
            }
            // 如果sum仍然小于k，说明即使包含整个数组也无法达到目标，提前退出。
            if (sum < k) {
                break;
            }
            // 下面的for循环试图从后往前缩小窗口大小，以寻找更短的满足条件的子数组。
            for (int i = current - 1, s = 0; i >= 0; i--) {
                // 恢复sum为其上一个状态（即未加入nums[i]的状态）
                sum = s;
                // 更新s为加入nums[i]后的按位或结果
                s |= nums[i];
                // 一旦找到满足条件的子数组，更新最小长度并跳出循环。
                if (s >= k) {
                    res = Math.min(res, current - i);
                    break;
                }
            }
        }

        // 如果找到了满足条件的子数组，则返回其长度；否则返回-1表示不存在这样的子数组。
        if (res <= n) {
            return res;
        }
        return -1;
    }

    /**
     * @Description: 给你一个长度为 n 的整数数组 nums ，请你返回 nums 中最 接近 0 的数字。
     * 如果有多个答案，请你返回它们中的 最大值 。
     * 示例 1：
     * 输入：nums = [-4,-2,1,4,8]
     * 输出：1
     * 解释：
     * -4 到 0 的距离为 |-4| = 4 。
     * -2 到 0 的距离为 |-2| = 2 。
     * 1 到 0 的距离为 |1| = 1 。
     * 4 到 0 的距离为 |4| = 4 。
     * 8 到 0 的距离为 |8| = 8 。
     * 所以，数组中距离 0 最近的数字为 1 。
     * <p>
     * 示例 2：
     * 输入：nums = [2,-1,1]
     * 输出：1
     * 解释：1 和 -1 都是距离 0 最近的数字，所以返回较大值 1 。
     * 提示：
     * 1 <= n <= 1000
     * -105 <= nums[i] <= 105
     * @param: [int[]]
     * @return: int
     * @Author: zhanglinxin
     * @date: 2025/1/20 15:13
     */

    public int findClosestNumber(int[] nums) {
        int abs = nums[0] > 0 ? nums[0] : -nums[0];
        int corrent = nums[0];
        for (int num : nums) {
            int abs1 = num > 0 ? num : -num;
            if (abs1 < abs || (abs1 == abs && num > corrent)) {
                corrent = num;
                abs = abs1;
            }
        }
        return corrent;
    }

    /**
     * @Description: 一张桌子上总共有 n 个硬币 栈 。每个栈有 正整数 个带面值的硬币。
     * 每一次操作中，你可以从任意一个栈的 顶部 取出 1 个硬币，从栈中移除它，并放入你的钱包里。
     * 给你一个列表 piles ，其中 piles[i] 是一个整数数组，分别表示第 i 个栈里 从顶到底 的硬币面值。
     * 同时给你一个正整数 k ，请你返回在 恰好 进行 k 次操作的前提下，你钱包里硬币面值之和 最大为多少 。
     * <p>
     * 示例 1：
     * 输入：piles = [[1,100,3],[7,8,9]], k = 2
     * 输出：101
     * 解释：
     * 上图展示了几种选择 k 个硬币的不同方法。
     * 我们可以得到的最大面值为 101 。
     * <p>
     * 示例 2：
     * 输入：piles = [[100],[100],[100],[100],[100],[100],[1,1,1,1,1,1,700]], k = 7
     * 输出：706
     * 解释：
     * 如果我们所有硬币都从最后一个栈中取，可以得到最大面值和。
     * @param: [java.util.List<java.util.List < java.lang.Integer>>, int]
     * @return: int
     * @Author: zhanglinxin
     * @date: 2025/1/21 09:32
     */
    public int maxValueOfCoins(List<List<Integer>> piles, int k) {
        // 创建一个数组f，其中f[i]表示恰好选择了i个硬币时可以获得的最大价值。
        // 初始化所有值为-1，表示尚未计算的状态。
        int[] f = new int[k + 1];
        Arrays.fill(f, -1);
        // 当没有选择任何硬币时，价值为0。
        f[0] = 0;
        // 遍历每一堆硬币。
        for (List<Integer> pile : piles) {
            // 从后向前遍历可能的选择数量，以确保在更新f[i]时，之前的状态未被当前循环改变。
            for (int i = k; i > 0; --i) {
                int value = 0;
                // 对于当前堆中的每一个硬币，计算选择不同数量硬币时的价值。
                for (int t = 1; t <= pile.size() && t <= i; ++t) {
                    // 累加当前堆中前t个硬币的总价值。
                    value += pile.get(t - 1);
                    // 如果剩余的容量足够放下这t个硬币，并且剩余容量下的最大值已计算过（即不等于-1），
                    // 则更新f[i]为当前值和新计算值之间的较大者。
                    if (f[i - t] != -1) {
                        f[i] = Math.max(f[i], f[i - t] + value);
                    }
                }
            }
        }
        // 返回选择了k个硬币时的最大价值。
        return f[k];
    }

    public int maxValueOfCoins1(List<List<Integer>> piles, int k) {
        // 获取硬币堆的数量。
        int n = piles.size();
        // 创建一个数组tS，其中tS[i]表示前i+1堆硬币的总数量。
        int[] tS = new int[n];
        // 第一堆硬币的数量。
        tS[0] = piles.getFirst().size();
        for (int i = 1; i < n; i++) {
            // 累计每一堆的硬币数。
            tS[i] = tS[i - 1] + piles.get(i).size();
        }

        // 创建一个二维数组sums，其中sums[i][j]表示第i堆中前j+1个硬币的总价值。
        int[][] sums = new int[n][];
        for (int i = 0; i < n; i++) {
            List<Integer> pile = piles.get(i);
            sums[i] = new int[pile.size()];
            // 第一个硬币的价值。
            sums[i][0] = pile.getFirst();
            for (int j = 1; j < pile.size(); j++) {
                // 累加每堆中硬币的价值。
                sums[i][j] = sums[i][j - 1] + pile.get(j);
            }
        }

        // 创建一个二维动态规划表dp，其中dp[i][j]表示从前i+1堆中选择不超过j个硬币时可以获得的最大价值。
        int[][] dp = new int[n][k + 1];
        // 用于存储最终的最大值。
        int max = -1;
        // 初始化第一堆的情况。
        for (int i = 0; i < tS[0] && i < k; i++) {
            // 计算从第一堆中选择不同数量硬币的最大价值。
            dp[0][i + 1] = dp[0][i] + piles.getFirst().get(i);
            // 更新最大值。
            max = Math.max(max, dp[0][i + 1]);
        }

        // 动态规划：遍历每一个堆，并更新dp表。
        // 对于每个堆（从第二个开始）。
        for (int i = 1; i < n; i++) {
            // 当前堆的大小。
            int size = piles.get(i).size();
            // 遍历可能的选择数量。
            for (int j = 0; j <= k && j <= tS[i]; j++) {
                // 初始状态为不选择当前堆中的任何硬币。
                int t = dp[i - 1][j];
                // 尝试从当前堆中选择不同的硬币数量。
                for (int l = 0; l < j && l < size; l++) {
                    // 更新状态。
                    t = Math.max(t, dp[i - 1][j - l - 1] + sums[i][l]);
                }
                // 存储结果到dp表中。
                dp[i][j] = t;
                // 更新最大值。
                max = Math.max(max, t);
            }
        }
        return max;
    }

    /**
     * @Description: 有 3n 堆数目不一的硬币，你和你的朋友们打算按以下方式分硬币：
     * <p>
     * 每一轮中，你将会选出 任意 3 堆硬币（不一定连续）。
     * Alice 将会取走硬币数量最多的那一堆。
     * 你将会取走硬币数量第二多的那一堆。
     * Bob 将会取走最后一堆。
     * 重复这个过程，直到没有更多硬币。
     * 给你一个整数数组 piles ，其中 piles[i] 是第 i 堆中硬币的数目。
     * <p>
     * 返回你可以获得的最大硬币数目。
     * <p>
     * 示例 1：
     * 输入：piles = [2,4,1,2,7,8]
     * 输出：9
     * 解释：选出 (2, 7, 8) ，Alice 取走 8 枚硬币的那堆，你取走 7 枚硬币的那堆，Bob 取走最后一堆。
     * 选出 (1, 2, 4) , Alice 取走 4 枚硬币的那堆，你取走 2 枚硬币的那堆，Bob 取走最后一堆。
     * 你可以获得的最大硬币数目：7 + 2 = 9.
     * 考虑另外一种情况，如果选出的是 (1, 2, 8) 和 (2, 4, 7) ，你就只能得到 2 + 4 = 6 枚硬币，这不是最优解。
     * <p>
     * 示例 2：
     * 输入：piles = [2,4,5]
     * 输出：4
     * <p>
     * 示例 3：
     * 输入：piles = [9,8,7,6,5,1,2,3,4]
     * 输出：18
     * @param: [int[]]
     * @return: int
     * @Author: zhanglinxin
     * @date: 2025/1/22 08:45
     */
    public int maxCoins(int[] piles) {
        int k = piles.length / 3;
        int max = 0;
        Arrays.sort(piles);
        for (; k > 0; k--) {
            max += piles[piles.length - 2 * k];
        }
        return max;
    }

    public int maxCoins1(int[] piles) {
        // 创建一个长度为10001的数组arr用于统计每个可能的石子数量出现的次数。
        // 数组索引代表石子的数量，值代表该数量出现的次数。
        int[] arr = new int[10001];

        // 遍历输入数组piles，对于每一个元素pile（即每一堆石子的数量），
        // 在arr数组中对应的位置增加计数值。
        for (int pile : piles) {
            arr[pile]++;
        }

        // 初始化变量cur用于临时存储当前循环中要处理的数量；
        // res用于累加所选石子堆的价值之和；
        // flag用于跟踪处理过程中的一些状态信息，具体作用见下文。
        int cur, res = 0, flag = 0;

        // 计算需要选择的堆的数量k，等于piles数组长度的三分之一。
        // 这个条件是基于游戏规则，每三堆中你只能选择一堆。
        int k = piles.length / 3;

        // 开始从最大可能的石子数量（10000）递减到最小（1），同时确保还有剩余需要选取的堆（k>0）。
        for (int i = 10000; i > 0 && k > 0; i--) {
            // 如果当前石子数量i存在于piles中（即有堆包含恰好i个石子）
            if (arr[i] > 0) {
                // 计算本次循环中可以选取的堆的数量。
                // 使用位移操作符>>1来代替除以2的操作，意味着尝试选取一半的堆，如果arr[i]是奇数则向上取整。
                // Math.min(k, ...)确保不会超过还需要选取的堆的数量k。
                cur = Math.min(k, ((arr[i] + flag) >> 1));

                // 更新flag。当arr[i]是奇数时翻转flag的值，这影响了上述cur的计算方式，
                // 确保总是尽可能平均地选取堆，这里是为了应对arr[i]为奇数的情况。
                flag ^= (arr[i] & 1);

                // 将当前石子数量i乘以可以选取的堆的数量cur，并将结果累加到res上，
                // 以此来计算总和。
                res += i * cur;

                // 减少剩余需要选取的堆的数量k。
                k -= cur;
            }
        }

        // 返回计算的结果res，即按照特定规则可以获取的最大石子数量。
        return res;
    }

    /**
     * @Description: 有一棵由 n 个节点组成的无向树，以 0  为根节点，节点编号从 0 到 n - 1 。
     * 给你一个长度为 n - 1 的二维 整数 数组 edges ，其中 edges[i] = [ai, bi]
     * 表示在树上的节点 ai 和 bi 之间存在一条边。
     * 另给你一个下标从 0 开始、长度为 n 的数组 coins 和一个整数 k ，其中 coins[i] 表示节点 i 处的金币数量。
     * 从根节点开始，你必须收集所有金币。要想收集节点上的金币，必须先收集该节点的祖先节点上的金币。
     * 节点 i 上的金币可以用下述方法之一进行收集：
     * 收集所有金币，得到共计 coins[i] - k 点积分。如果 coins[i] - k 是负数，你将会失去 abs(coins[i] - k) 点积分。
     * 收集所有金币，得到共计 floor(coins[i] / 2) 点积分。如果采用这种方法，
     * 节点 i 子树中所有节点 j 的金币数 coins[j] 将会减少至 floor(coins[j] / 2) 。
     * 返回收集 所有 树节点的金币之后可以获得的最大积分。
     * <p>
     * 示例1
     * 输入：edges = [[0,1],[1,2],[2,3]], coins = [10,10,3,3], k = 5
     * 输出：11
     * 解释：
     * 使用第一种方法收集节点 0 上的所有金币。总积分 = 10 - 5 = 5 。
     * 使用第一种方法收集节点 1 上的所有金币。总积分 = 5 + (10 - 5) = 10 。
     * 使用第二种方法收集节点 2 上的所有金币。所以节点 3 上的金币将会变为 floor(3 / 2) = 1 ，总积分 = 10 + floor(3 / 2) = 11 。
     * 使用第二种方法收集节点 3 上的所有金币。总积分 =  11 + floor(1 / 2) = 11.
     * 可以证明收集所有节点上的金币能获得的最大积分是 11 。
     * <p>
     * 示例2
     * 输入：edges = [[0,1],[0,2]], coins = [8,4,4], k = 0
     * 输出：16
     * 解释：
     * 使用第一种方法收集所有节点上的金币，因此，总积分 = (8 - 0) + (4 - 0) + (4 - 0) = 16 。
     * <p>
     * <p>
     * 提示：
     * <p>
     * n == coins.length
     * 2 <= n <= 105
     * 0 <= coins[i] <= 104
     * edges.length == n - 1
     * 0 <= edges[i][0], edges[i][1] < n
     * 0 <= k <= 104
     * @param: [int[][], int[], int]
     * @return: int
     * @Author: zhanglinxin
     * @date: 2025/1/23 08:35
     */
    public int maximumPoints(int[][] edges, int[] coins, int k) {
        int n = coins.length;

        // 创建邻接表来表示树
        ArrayList[] adjacency = new ArrayList[n];
        Arrays.setAll(adjacency, i -> new ArrayList<>());

        // 填充邻接表
        for (int[] edge : edges) {
            int a = edge[0], b = edge[1];
            adjacency[a].add(b);
            adjacency[b].add(a);
        }

        // 从根节点（编号为0）开始进行深度优先搜索
        return dfs(adjacency, -1, 0, coins, k)[0];
    }

    /**
     * 深度优先搜索函数，计算每个节点在不同策略下的最大积分。
     *
     * @param adjacency 邻接表表示的树
     * @param fa        父节点
     * @param node      当前节点
     * @param coins     每个节点的金币数量
     * @param k         减少的固定值
     * @return 包含当前节点在不同策略下的最大积分的数组
     */
    public int[] dfs(List<Integer>[] adjacency, int fa, int node, int[] coins, int k) {
        // s[i] 表示在当前节点应用第 i 种策略时的最大积分
        int[] s = new int[14];

        // 遍历当前节点的所有子节点
        for (int child : adjacency[node]) {
            // 跳过父节点
            if (fa == child) {
                continue;
            }
            // 递归计算子节点的结果
            int[] fy = dfs(adjacency, node, child, coins, k);
            // 将子节点的结果累加到当前节点的结果中
            for (int i = 0; i < 13; i++) {
                s[i] += fy[i];
            }
        }

        // 计算当前节点在不同策略下的最大积分
        for (int i = 0; i < 13; i++) {
            s[i] = Math.max(
                    // 策略一：收集所有金币，得到 coins[node] / (2^i) - k 点积分
                    (coins[node] >> i) + s[i] - k,
                    // 策略二：收集一半金币，得到 coins[node] / (2^(i+1)) 点积分
                    (coins[node] >> (i + 1)) + s[i + 1]
            );
        }

        // 特殊处理第 13 种策略
        s[13] = (coins[node] >> 13) + s[13] - k;

        return s;
    }


    public static void main(String[] args) {
        Solution202501 solution202501 = new Solution202501();
        int[][] edges = {{0, 1}, {1, 2}, {2, 3}};
        int[] coins = {10, 10, 3, 3};
        int k = 5;
        int shortestSubArray = solution202501.maximumPoints(edges, coins, k);
        System.out.println(shortestSubArray);
    }
}
